package two.chapter_1.c1_4;

public class Ex1_4_6 {


    /**
     * N+N/2+N/4+...+1 ~2N
     *
     *
     * @param N
     * @return
     */
    private static int a(int N) {
        int sum = 0;
        for (int n = N; n > 0; n /= 2) {
            for (int i = 0; i < n; i++) {
                sum++;
            }
        }
        return sum;
    }

    /**
     * 1+2+4+...+N =2N-1 ~2N
     * @param N
     * @return
     */
    private static int b(int N) {
        int sum = 0;
        for (int i = 1; i < N; i *= 2) { //
            for (int j = 0; j < i; j++) {//
                sum++;
            }
        }
        return sum;
    }

    /**
     * NlogN
     * @param N
     * @return
     */
    private static int c(int N) {
        int sum = 0;
        for (int i = 1; i < N; i *= 2) {//logN
            for (int j = 0; j < N; j++) {//N
                sum++;
            }
        }
        return sum;
    }
}
